package com.example.demo.huawei;

//给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
//
//
//
//示例 1：
//
//输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
//输出：6
//解释：[1,1,1,0,0,1,1,1,1,1,1]
//粗体数字从 0 翻转到 1，最长的子数组长度为 6。
//示例 2：
//
//输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
//输出：10
//解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]


import java.util.Arrays;

//转化：找出最长的子数组，0的个数不超过k个
public class Main15 {
    public static void main(String[] args) {
        int[] nums1 = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
        int[] nums2 = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1};
        System.out.println(new Main15().longestOnes2(nums1, 2));
//        System.out.println(new Main15().longestOnes2(nums2, 3));
    }

    /**
     * 穷举 效率太低了
     *
     * @param nums
     * @param k
     * @return
     */
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j <= nums.length; j++) {
                int[] tempArr = Arrays.copyOfRange(nums, i, j);
                int countZero = countZero(tempArr);
                if (countZero <= k) {
                    maxLength = Math.max(maxLength, tempArr.length);
                }
            }
        }
        return maxLength;
    }


    private int countZero(int[] arr) {
        int sum = 0;
        for (int j : arr) {
            if (j == 0) {
                sum++;
            }
        }
        return sum;
    }

    /**
     * 固定left为第一个位置，移动right,当数字是1时，忽略1，如果是0，计数。
     * 当zero统计的数字大于k时right不动。移动left，当left越过一个0，在开始继续移动right
     * //输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
     * //输出：6
     *
     * @param nums
     * @param k
     * @return
     */

    //输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
    //输出：6
    public int longestOnes2(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int count = 0;
        int ret = 0;
        while (right < nums.length && left < nums.length) {
            if (nums[right] == 0) {
                count++;
            }
            while (count > k) {
                if (nums[left] == 0) {
                    count--;
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}
